package com.atguigu.interview.algo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.TimeUnit;

/**
 * @Author : Jungle
 * @Description :  基于线程的睡眠时间对数组进行排序
 */
public class SortDemo {
    static List list = new ArrayList();

    static class ArraySort implements Runnable {
        private Integer num;

        public ArraySort(Integer num) {
            this.num = num;
        }


        @Override
        public void run() {
            try {
                TimeUnit.MILLISECONDS.sleep(this.num);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //System.out.println(this.num);
            list.add(this.num);

        }
    }

    public static void main(String[] args) {
        int[] ints = {1, 2, 9, 18, 3};

        //for (int anInt : ints) {
        //    new Thread(new ArraySort(anInt)).start();
        //}
        //
        //while (Thread.activeCount() > 2) {
        //    Thread.yield();
        //}
        //System.out.println(list);

        //bubSort(ints);
        //quickSort(ints,);
        selectSort(ints);
        Arrays.stream(ints).forEach(System.out::println);
    }

    /**
     * 冒泡排序
     * 多个数字来排序，两两相比小靠前，外层循环n-1，内层循环n-1-i
     */
    private static void bubSort(int[] ints) {
        for (int i = 0; i < ints.length - 1; i++) {
            for (int j = 0; j < ints.length - 1 - i; j++) {
                if (ints[j] > ints[j + 1]) {
                    int temp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = temp;
                }
            }
        }
    }


    /**
     * 选择排序
     */
    private static void selectSort(int[] arr) {
        //for (int i = 0; i < arr.length - 1; i++) {
        //    // 标记最小数字的下标
        //    int min = i;
        //    //内层循环控制查找最小值（未排序序列）的范围
        //    for (int j = i; j < arr.length; j++) {
        //        if (arr[j] < arr[min]) {
        //            min = j;
        //        }
        //    }
        //    //将最小数和未排序的开头位置进行交换
        //    if (min != i) {
        //        int temp = arr[min];
        //        arr[min] = arr[i];
        //        arr[i] = temp;
        //    }
        //}
        /**
         * 外层和内层比
         */
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

    }


    /**
     * 快速排序,前提是有顺序的数组
     *
     * @param arr
     * @param start
     * @param end
     */
    public static void quickSort(int[] arr, int start, int end) {

        if (start > end) {
            return;
        }
        //求基准数位置
        int pivot = pivot(arr, start, end);
        //按照基准位置将数据分成两部分，递归排序
        quickSort(arr, start, pivot - 1);
        quickSort(arr, pivot + 1, end);
    }

    /**
     * 求基准位置
     *
     * @param arr
     * @param start
     * @param end
     * @return
     */
    public static int pivot(int[] arr, int start, int end) {
        //定义基准数
        int pivot = start;
        //定义左下标和右下标
        int left = start;
        int right = end;
        //循环移动
        while (left != right) {
            //如果右坐标的值比基准数大就向左移动
            while (left < right && arr[right] >= arr[pivot]) {
                right--;
            }
            //如果左下标的值比基准数小就向右移动
            while (left < right && arr[left] <= arr[pivot]) {
                left++;
            }
            //交换左右下标的数据
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        //将重合位置的数据和基准数交换
        int temp = arr[left];
        arr[left] = arr[pivot];
        arr[pivot] = temp;
        //返回中间位置
        return left;
    }


}
